package leetcode;

/**
 * Created with IntelliJ IDEA.
 * User: Ghost
 * Date: 14-5-30
 * Time: 下午8:01
 * To change this template use File | Settings | File Templates.
 */
class ListNode {
       int val;
         ListNode next;
         ListNode(int x) {
             val = x;
             next = null;
        }
     }
public class Solution4 {
    public ListNode sort(ListNode head){
        if(head==null || head.next==null){
            return head;
        }
        else{
            int i=0;
            ListNode head1 = head;
            while(head1!=null){
                i++;
                head1 = head1.next;
            }
            int j=0;
            ListNode head2 = head;
            while(j<i/2-1){
                head2 = head2.next;
                j++;
            }
            head1 = head2.next;
            head2.next = null;

            ListNode head11 = sort(head1);
            ListNode head22 = sort(head);
            ListNode headFinal = merge(head11,head22);
            return headFinal;
        }
    }
    public ListNode merge(ListNode head1,ListNode head2){
        ListNode headTmp1,headTmp2,headlast1,headlast2,head;
        headlast1 = null;
        headlast2 = null;
        head = head2;
        headTmp2 = head2;
        headTmp1 = head1;
        if(headTmp2==null){
            return headTmp1;
        }
        while(headTmp1!=null){
            if(headTmp1.val>headTmp2.val){
                for(;headTmp2!=null && headTmp1.val>headTmp2.val;headlast2=headTmp2,headTmp2=headTmp2.next);
                if(headTmp2==null){
                    headlast2.next = headTmp1;
                    for(;headTmp1!=null;headTmp1 = headTmp1.next);
                }
                else{
                    headlast2.next = headTmp1;
                    headlast1 = headTmp1;
                    headTmp1 = headTmp1.next;
                    headlast1.next = headTmp2;
                    headTmp2 = head;
                }
            }
            else{
                head = headTmp1;
                headTmp1 = headTmp1.next;
                head.next = headTmp2;
                headTmp2 = head;
            }
        }

        return head;
    }
    public ListNode sortList(ListNode head) {
        if(head==null){
            return head;
        }
        int i=0;
        ListNode head1 = head;
        while(head1!=null){
            i++;
            head1 = head1.next;
        }
        int j=0;
        ListNode head2 = head;
        while(j<i/2-1){
            head2 = head2.next;
            j++;
        }
        head1 = head2.next;
        head2.next = null;

        ListNode head11 = sort(head1);
        ListNode head22 = sort(head);
        ListNode headFinal = merge(head11,head22);
        return headFinal;
    }
    public static void main(String[] args){
        ListNode A = new ListNode(4);
       /* A.next = new ListNode(19);
         A.next.next = new ListNode(14);
        A.next.next.next = new ListNode(5);
        A.next.next.next.next= new ListNode(-3);
        A.next.next.next.next.next= new ListNode(1);
        A.next.next.next.next.next.next= new ListNode(8);
        A.next.next.next.next.next.next.next= new ListNode(5);
        A.next.next.next.next.next.next.next.next= new ListNode(11);
        A.next.next.next.next.next.next.next.next.next= new ListNode(15);*/
        Solution4 solution4 = new Solution4();
        ListNode B = solution4.sortList(A);
        System.out.println(B.val);
      /* System.out.println(B.next.val);
        System.out.println(B.next.next.val );
        System.out.println(B.next.next.next.val );
        System.out.println(B.next.next.next.next.val );
        System.out.println(B.next.next.next.next.next.val );
        System.out.println(B.next.next.next.next.next.next.val );
        System.out.println(B.next.next.next.next.next.next.next.val );
        System.out.println(B.next.next.next.next.next.next.next.next.val );
        System.out.println(B.next.next.next.next.next.next.next.next.next.val );*/
       /*System.out.println(B.next.next.next.val );*/
    }
}
